public class MaxPathSum {

    public int maxPathSum1(TreeNode root) {
        Info2 info = process(root);
        return Math.max(info.maxDeep, info.maxHeight);
    }

    public Info2 process(TreeNode node) {
        if (node == null) return new Info2(0, Integer.MIN_VALUE);
        if (node.left ==  null && node.right == null) return new Info2(node.val, node.val);
        Info2 infoL = process(node.left);
        Info2 infoR = process(node.right);
        int lH = infoL.maxHeight > 0 ? infoL.maxHeight : 0;
        int rH = infoR.maxHeight > 0 ? infoR.maxHeight : 0;
        int maxHeight = Math.max(lH, rH) + node.val;
        int maxDeep = Math.max(Math.max(infoL.maxDeep, infoR.maxDeep), infoR.maxHeight + infoL.maxHeight + node.val);
        return new Info2(maxHeight, maxDeep);
    }

    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        process1(root);
        return ans;
    }

    public int process1(TreeNode node) {
        if (node == null) return 0;
        int l = Math.max(0, process1(node.left));
        int r = Math.max(0, process1(node.right));
        ans = Math.max(ans, l + r + node.val);
        return node.val + Math.max(l, r);
    }
}

class Info2 {
    public int maxHeight;
    public int maxDeep;

    public Info2(int maxHeight, int maxDeep) {
        this.maxHeight = maxHeight;
        this.maxDeep = maxDeep;
    }
}
